# -*- coding: utf-8 -*-

'''
radix.py
Created on Junho de 2013
@author: Vlad Bagrin, http://codehost.wordpress.com/2011/07/22/radix-sort/

@compiled:
Ricardo Barros, ESTIG,  EI pós-laboral n.º 5137
Sergio Santos, ESTIG,  EI pós-laboral n.º 5626
'''

"""
O algoritmo "Radix Sort"

Tempo de execução:
    Pior cenário O(nk).
    (onde "n" é o número de chaves, e "k" é o comprimento médio da chave)


Carateristicas:
Não opera por comparação como a maioria dos algoritmos de ordenação.

Trabalha ordenando primeiro os dígitos menos significativos
(da direita para a esquerda).

Está associado ao conjunto de dígitos que podem existir num número.

O total de iterações depende do número máximo de dígitos que 
o número pode ter.

Em muitas aplicações em que é necessário velocidade, o radix sort melhora 
as ordenações por comparação, como heapsort e o mergesort, que necessitam 
de O(n log n) comparações, onde "n" é o número de itens a serem ordenados. 
Em compensação, algoritmos de ordenação baseados em comparações oferecem 
flexibilidade por serem aptos a ordenar de outras formas que não a lexicográfica.
No entanto, essa habilidade é de pouca importância em várias aplicações práticas.

BIBLIOGRAFIA:
http://codehost.wordpress.com/category/prolog/
http://prezi.com/h-reofcisvxu/radix-sort/
http://pt.wikipedia.org/wiki/Radix_sort

Como utilizar:
 - EXEMPLO: Ordenação do array A:
 
    A = [10, 11, 12, 3, 13, 13, 14, 15, 16, 17, 2, 4, 5, 7, 1, 2, 3, 6, 20, 21]
    print "antes A: ", A
    radixSortNumbers(A)
    print "depois A:", A

RESULTADO:
antes A:  [10, 11, 12, 3, 13, 13, 14, 15, 16, 17, 2, 4, 5, 7, 1, 2, 3, 6, 20, 21]
depois A: [1, 2, 2, 3, 3, 4, 5, 6, 7, 10, 11, 12, 13, 13, 14, 15, 16, 17, 20, 21]
>>>
"""


import math # Especially in radixSortNumbers
 


# Radix sort for numbers in base 10
def radixSortNumbers(array):
    maxLen = -1
    for number in array: # Find longest number, in digits
        try:
            numLen = int(math.log10(number)) + 1
        except ValueError:
            numLen = 1
        #numLen = int(math.log10(number)) + 1
        if numLen > maxLen:
            maxLen = numLen
    buckets = [[] for i in range(0, 20)] # Buckets for each digit
    for digit in range(0, maxLen):
        for number in array:
            buckets[number / 10**digit % 10].append(number)
        del array[:]
        for bucket in buckets:
            array.extend(bucket)
            del bucket[:]
    return array

# Radix sort for variable length strings
def radixSortString(array):
    maxLen = -1
    for string in array: # Find longest string
        strLen = len(string)
        if strLen > maxLen:
            maxLen = strLen
    oa = ord('a') - 1; # First character code
    oz = ord('z') - 1; # Last character code
    n = oz - oa + 2; # Number of buckets (+empty character)
    buckets = [[] for i in range(0, n)] # The buckets
    for position in reversed(range(0, maxLen)):
        for string in array:
            index = 0 # Assume "empty" character
            if position < len(string): # Might be within length
                index = ord(string[position]) - oa
            buckets[index].append(string) # Add to bucket
        del array[:]
        for bucket in buckets: # Reassemble array in new order
            array.extend(bucket)
            del bucket[:]
    return array
    
# Radix sort for fixed length strings
def radixSortFixedString(array):
    fixedLength = len(array[0])
    oa = ord('a'); # First character code
    oz = ord('z'); # Last character code
    n = oz - oa + 1; # Number of buckets
    buckets = [[] for i in range(0, n)] # The buckets
    for position in reversed(range(0, fixedLength)):
        for string in array:
            buckets[ord(string[position]) - oa].append(string) # Add to bucket
        del array[:]
        for bucket in buckets: # Reassemble array in new order
            array.extend(bucket)
            del bucket[:]
    return array


def main():
    A = [10, 11, 12, 3, 13, 13, 14, 15, 16, 17, 2, 4, 5, 7, 1, 2, 3, 6, 20, 21]
    print "antes A: ", A
    radixSortNumbers(A)
    print "depois A:", A

if __name__ == '__main__':
    main()